const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};

function preorderTraversal(root) {
    if (!root) {
        return []
    }
    let res = []
    let stack = [root]

    while (stack.length) { 
        // 弹出根节点
        let node = stack.pop()
        res.push(node.val)
        if (node.right) {
            // 右子树入栈
            stack.push(node.right)
        }
        if (node.left) {
            // 左子树入栈
            stack.push(node.left)
        }
    }
    return res
}
console.log(preorderTraversal(root));

var preorderTraversal2 = function(root, res = []) {
    const stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const node = stack.pop();
        if(!node) {
            res.push(stack.pop().val);
            continue;
        }
        if (node.right) stack.push(node.right); // 右
        if (node.left) stack.push(node.left); // 左
        stack.push(node); // 中
        stack.push(null);
    };
    return res;
};

console.log(preorderTraversal2(root));